package com.leetcode;

import java.util.ArrayList;

/**
 * 300. 最长递增子序列
 *
 * @author fy
 * @date 2022/3/29 22:23
 */
public class Solution300 {

    /**
     * 300. 最长递增子序列
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            int now = nums[i];
            for (int j = 0; j < i; j++) {
                int pre = nums[j];
                if (now > pre) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(dp[i], res);
        }
        return res;
    }


    private int peek() {
        return tail.get(tail.size() - 1);
    }

    private ArrayList<Integer> tail;

    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int last = nums[0];
        int max = 1;

        tail = new ArrayList<Integer>(len);
        tail.add(nums[0]);

        for (int i = 1; i < len; ++i) {
            if (nums[i] > peek()) {
                tail.add(nums[i]);
            } else {
                int l = 0, r = tail.size() - 1, mid = 0;
                while (l <= r) {
                    mid = l + ((r - l) >> 1);
                    if (nums[i] > tail.get(mid)) {
                        l = mid + 1;
                    } else if (nums[i] < tail.get(mid)) {
                        r = mid - 1;
                    } else {
                        l = mid;
                        break;
                    }
                }
                tail.set(l, nums[i]);

            }
        }

        return tail.size();
    }


    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 7, 10, 9, 2, 5, 3, 7};
        new Solution300().lengthOfLIS(nums);
    }
}
